package Q1305

import java.util.*
import kotlin.collections.ArrayList

/**
 * 两颗二傻搜索树中的所有元素
 * @author 23737
 * @date 2022.5.5
 */
class Main {

}

fun main() {
    var treeNode = TreeNode(2)
    var treeNode2 = TreeNode(1)
    var treeNode3 = TreeNode(4)
    var treeNode4 = TreeNode(1)
    var treeNode5 = TreeNode(0)
    var treeNode6 = TreeNode(3)
    treeNode.left = treeNode2
    treeNode.right = treeNode3

    treeNode4.left = treeNode5
    treeNode4.right = treeNode6

    var allElements = Solution().getAllElements(treeNode, treeNode4)
    for (allElement in allElements) {
        print(" $allElement ")
    }
}


class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun getAllElements(root1: TreeNode?, root2: TreeNode?): List<Int> {
        val res: MutableList<Int> = ArrayList<Int>()
        val queue: Deque<TreeNode> = LinkedList<TreeNode>()
        val queue2: Deque<TreeNode> = LinkedList<TreeNode>()
        if (root1 == null && root2 == null) {
            return res
        }
        if (root1 == null) {
            queue.offer(root2)
        } else {
            queue.offer(root1)
        }
        while (!queue.isEmpty()) {
            val poll = queue.poll()
            res.add(poll.`val`)
            if (poll.left != null) {
                queue.offer(poll.left)
            }
            if (poll.right != null) {
                queue.offer(poll.right)
            }
        }
        if (root2 == null || root1 == null) {
            res.sort()
            return res
        }
        queue2.offer(root2)
        while (!queue2.isEmpty()) {
            val poll = queue2.poll()
            res.add(poll.`val`)
            if (poll.left != null) {
                queue2.offer(poll.left)
            }
            if(poll.right != null){
                queue2.offer(poll.right)
            }
        }
        res.sort()
        return res
    }
}